Abstract
$Q$-learning is one of the most fundamental reinforcement learningalgorithms. It is widely believed that $Q$-learning with linear functionapproximation (i.e., linear $Q$-learning) suffers from possible divergenceuntil the recent work Meyn (2024) which establishes the ultimate almost sureboundedness of the iterates of linear $Q$-learning. Building on this success,this paper further establishes the first $L^2$ convergence rate of linear$Q$-learning iterates (to a bounded set). Similar to Meyn (2024), we do notmake any modification to the original linear $Q$-learning algorithm, do notmake any Bellman completeness assumption, and do not make any near-optimalityassumption on the behavior policy. All we need is an $\epsilon$-softmaxbehavior policy with an adaptive temperature. The key to our analysis is thegeneral result of stochastic approximations under Markovian noise withfast-changing transition functions. As a side product, we also use this generalresult to establish the $L^2$ convergence rate of tabular $Q$-learning with an$\epsilon$-softmax behavior policy, for which we rely on a novelpseudo-contraction property of the weighted Bellman optimality operator.